The problem can be found at the following link: Question Link
I approached this problem using a hashmap to store the remainder of the cumulative sum when divided by k
. The key idea is to find two indices with the same remainder to get a subarray whose sum is divisible by k
.
- I initialized a hashmap
mp
with an initial entry of {0, -1}, indicating that the sum 0 is seen at index -1. - I iterated through the array, updating the cumulative sum and calculating the remainder when divided by
k
. - To handle negative remainders, I added
k
to the remainder if it was negative. - If the remainder was already in the hashmap, I updated the maximum subarray length
out
by comparing it with the difference between the current index and the index stored in the hashmap for that remainder. Otherwise, I added a new entry in the hashmap. - The final result is the length of the longest subarray with a sum divisible by
k
.
- Time Complexity:
O(n)
, where n is the size of the array. The algorithm processes each element of the array once. - Auxiliary Space Complexity:
O(min(n, k))
, wheren
is the size of the array. The hashmapmp
stores at mostmin(n, k)
entries.
class Solution {
public:
int longSubarrWthSumDivByK(int arr[], int n, int k) {
unordered_map<int, int> mp;
mp[0] = -1;
int out = 0, sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
int rem = sum % k;
if (rem < 0)
rem += k;
if (mp.find(rem) != mp.end())
out = max(out, i - mp[rem]);
else
mp[rem] = i;
}
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.